#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution
{
public:
    vector<string> letterCombinations(string digits)
    {
        const vector<string> v = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        vector<string> finalresult;

        if (digits.empty())
        {
            return finalresult; // 如果输入为空，返回空集合
        }

        string curresult;
        backtrack(finalresult, v, digits, 0, curresult);
        return finalresult;

    }

private:
    void backtrack(vector<string>& finalresult, const vector<string>& v, const string& digits,
                    int i, string& curresult)
    {
        if(i == digits.size())
        {
            finalresult.push_back(curresult);
            return;
        }

        string allletter = v[digits[i]-'0'];
        for(auto letter : allletter)
        {
            curresult.push_back(letter);
            backtrack(finalresult, v, digits, i+1, curresult);
            curresult.pop_back();
        }
    }
};

int main()
{
    Solution solution;
    string digits = "23"; // 输入数字
    vector<string> result = solution.letterCombinations(digits);

    // 输出结果
    cout << "[";
    for (size_t i = 0; i < result.size(); ++i)
    {
        cout << "\"" << result[i] << "\"";
        if (i != result.size() - 1)
        {
            cout << ", ";
        }
    }
    cout << "]" << endl;

    return 0;
}


